package lc2;

import org.junit.Test;

public class Ex402 {
    class Solution {
        public String removeKdigits(String num, int k) {
            char[] cs = num.toCharArray();
            int n = cs.length;
            if (n == k) {
                return "0";
            }
            char[] stack = new char[n];
            int idx = -1, cnt = n - k; //cnt:还需要的字符个数
            for (int i = 0; i < n; i++) {
                while (n - i > cnt && idx >= 0 && stack[idx] > cs[i]) {
                    idx--;
                    cnt++;
                }
                if (cnt > 0) {
                    stack[++idx] = cs[i];
                    cnt--;
                }
            }
            StringBuilder sb = new StringBuilder(); 
            boolean start = false;
            for (int i = 0; i <= idx; i++) {
                if (!start && stack[i] != '0') {
                    start = true;
                }
                if (start) {
                    sb.append(stack[i]);
                }
            }
            String res = sb.toString();
            return res.isEmpty() ? "0" : res;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        System.out.println(s.removeKdigits("112"
        ,1));
    }
}
